<?php
// https://leetcode-cn.com/problems/longest-common-subsequence/solution/dong-tai-gui-hua-zhi-zui-chang-gong-gong-zi-xu-lie/

// 如果某个字符应该在 lcs 中，那么这个字符肯定同时存在于 s1 和 s2 中，因为 lcs 是最长公共子序列嘛

//用两个指针 i 和 j 从后往前遍历 s1 和 s2，如果 s1[i]==s2[j]，那么这个字符一定在 lcs 中；
//否则的话，s1[i] 和 s2[j] 这两个字符至少有一个不在 lcs 中，需要丢弃一个。

Class Solution
{
    public function longestCommonSubsequence($str1, $str2)
    {
        return $this->dp($str1, $str2, strlen($str1) - 1, strlen($str2)-1);
    }

    /**
     * @param $str1
     * @param $str2
     * @param $str1_pos
     * @param $str2_pos
     * @return int
     */
    public function dp($str1, $str2, $str1_pos, $str2_pos)
    {
        // 空串
        if ($str1_pos == -1 || $str2_pos == -1) {
            return 0;
        }

        // 找到一个 lcs 的元素，继续往前找
        if ($str1[$str1_pos] == $str2[$str2_pos]) {
            return $this->dp($str1, $str2, $str1_pos-1, $str2_pos-1) + 1;
        }

        // 谁能让 lcs 最长，就听谁的
        return max(
            $this->dp($str1, $str2,$str1_pos-1, $str2_pos),
            $this->dp($str1, $str2, $str1_pos, $str2_pos-1)
        );
    }
}